package com.zjj.algorithm.learning.atguigu.sort;

import java.util.Arrays;

/**
 * @author zjj_admin
 * @date 2022/11/14 20:17
 */
public class ShellSort {

    public static void main(String[] args) {
        int[] arr = new int[]{6, 0, 2, 3, 5, 9};
        shellSort2(arr);


        //测试排 80000 个数据用时
//        int[] arr = new int[80000];
//        for (int i = 0; i < arr.length; i++) {
//            arr[i] = (int) (Math.random() * 800000);
//        }
//        long time1 = System.currentTimeMillis();
//
//        shellSort2(arr);
//        long time2 = System.currentTimeMillis();
//        System.out.printf("使用选择排序，排 %d 个数据，用时 %s ms", arr.length, (time2 - time1));

    }


    /**
     * 位移法
     * 使用选择排序，排 80000 个数据，用时 15 ms
     *
     * @param arr
     */
    public static void shellSort2(int[] arr) {

        int temp;
        int count = 0;
        for (int gap = arr.length / 2; gap > 0; gap = gap / 2) {
            count++;
            for (int i = gap; i < arr.length; i++) {
                int j = i;
                temp = arr[i];
                while (j - gap >= 0 && temp < arr[j - gap]) {
                    arr[j] = arr[j - gap];
                    //继续将j向前移动一个gap，判断 temp 是不是继续小于这个值，直到 j - gap < 0 结束，不然一直比较
                    j = j - gap;
                }
                arr[j] = temp;
            }
//            System.out.printf("第 %d 次排序之后：%s \n", count, Arrays.toString(arr));
        }

    }


    /**
     * 使用交换法
     * 使用选择排序，排 80000 个数据，用时 约1 - 2 分钟
     *
     * @param arr
     */
    public static void shellSort1(int[] arr) {


        int temp;
        int count = 0;
        for (int gap = arr.length / 2; gap > 0; gap = gap / 2) {
            count++;
            for (int i = gap; i < arr.length; i++) {
                for (int j = 0; j <= arr.length - gap; j++) {

                    if (arr[j] > arr[i]) {
                        temp = arr[i];
                        arr[i] = arr[j];
                        arr[j] = temp;
                    }
                }
            }
//            System.out.printf("第 %d 次排序之后：%s \n" ,count, Arrays.toString(arr));
        }


        //以下分析
//        int temp;
//        for (int i = 5; i < 10; i++) {
//            for (int j = 0; j <= 5 ; j ++){
//                if(arr[j] > arr [i]){
//                    temp = arr[i];
//                    arr[i] = arr[j];
//                    arr[j] = temp;
//                }
//            }
//        }
//        System.out.println("第1次排序之后：" + Arrays.toString(arr));
//
//        for (int i = 2; i < 10; i++) {
//            for (int j = 0; j <= 8 ; j ++){
//                if(arr[j] > arr [i]){
//                    temp = arr[i];
//                    arr[i] = arr[j];
//                    arr[j] = temp;
//                }
//            }
//        }
//        System.out.println("第2次排序之后：" + Arrays.toString(arr));

    }

}
